package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

/**
 * 思路：
 * 从左右子树分别获取
 * - 子树内的最大路径和
 * - 子树内以根节点为起点的最大路径和
 * <p>
 * 这样就知道了 本节点的最大路径和
 *
 * @author qidi
 * @date 2022-01-10 10:44:19
 */
class Q0124_BinaryTreeMaximumPathSum {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        private class Data {
            int maxPath = 0;
            int rootMax = 0;

            public Data(int maxPath, int rootMax) {
                // 做大路径和
                this.maxPath = maxPath;
                // 以根节点为起始节点的最大路径和
                this.rootMax = rootMax;
            }

            public Data() {

            }
        }

        public int maxPathSum(TreeNode root) {
            return process(root).maxPath;
        }

        private Data process(TreeNode node) {
            if (node == null) return new Data(-1000, -1000);
            if (node.left == null && node.right == null) {
                return new Data(node.val, node.val);
            }

            Data leftData = process(node.left);
            Data rightData = process(node.right);

            Data data = new Data();

            data.rootMax = Math.max(node.val, Math.max(node.val + leftData.rootMax, node.val + rightData.rootMax));

            // 节点最大的路径为 左子树路径和、 左右子树路径和、 当前节点的加上左右子树以根节点为起点的路径和中最大的一个
            int subMaxPath = Math.max(leftData.maxPath, rightData.maxPath);

            int curRootMax = Math.max(leftData.rootMax, rightData.rootMax) + node.val;

            curRootMax = Math.max(curRootMax, leftData.rootMax + rightData.rootMax + node.val);

            curRootMax = Math.max(node.val, curRootMax);

            data.maxPath = Math.max(subMaxPath, curRootMax);

            return data;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0124_BinaryTreeMaximumPathSum().new Solution();
        BTreeUtil util = BTreeUtil.getInstance();
        System.out.println(solution.maxPathSum(util.generateFromArray(1, 2, null, 3, null, 4, null, 5)));
        System.out.println(solution.maxPathSum(util.generateFromArray(1, 2)));
        System.out.println(solution.maxPathSum(util.generateFromArray(1, -2, -3)));
        System.out.println(solution.maxPathSum(util.generateFromArray(-1, 2, 3)));
        System.out.println(solution.maxPathSum(util.generateFromArray(-10, 9, 20, null, null, 15, 7)));
    }
}